[APIO2014]-序列分割

斜率优化

题目链接

啊。。。好恶心。。最后逼着我去对拍【面孔扭曲】也算很有意义了！趁机复习一波斜率优化。。

可以发现，答案和分割顺序好像并没有关系，所以我们可以默认为从左向右分割（这样最方便

设 f[i, j] 表示前 j 个分割了 i 次。那么方程就是：f[i, j] = max{f[i - 1][k] + s[k]·(s[j]·s[k])}
(其中 s[i] 表示 a[1] ~ a[i] 的和)

如果决策 k1 < k2（k2更优：

=>

这是一个斜率优化的式子，然后就是套路了。祝玩耍愉快。

code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
typedef long long ll;
int n, K, a[N], q[N], r;
ll sum[N], f[2][N];

double slope(int j, int k) {
    if (sum[j] == sum[k]) return -1e18;
    return (double)(sum[k] * sum[k] - sum[j] * sum[j] + f[(r & 1) ^ 1][j] - f[(r & 1) ^ 1][k]) / (double)(sum[k] - sum[j]);
}

int main() {
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
    for (r = 1; r <= K; r++) {
        int head = 1, tail = 0;
        for (int i = r; i <= n; i++) {
            while (head < tail && slope(q[head], q[head + 1]) < sum[i]) head++;
            int t = q[head];
            f[r & 1][i] = f[(r & 1) ^ 1][t] + (sum[i] - sum[t]) * sum[t];
            while (head < tail && slope(q[tail - 1], q[tail]) > slope(q[tail], i)) tail--;
            q[++tail] = i;
        }
    }
    printf("%lld\n", f[K & 1][n]);
    return 0;
}